Problem
Description
营业额统计 Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况： 该天的最小波动值 当最小波动值越大时，就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。 第一天的最小波动值为第一天的营业额。 输入输出要求
Input
第一行为正整数 ，表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数(有可能有负数) ，表示第i
天公司的营业额。
天数n<=32767,
每天的营业额ai <= 1,000,000。
最后结果T<=2^31
Output
输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。
Sample Input
6
5
1
2
5
4
6
Sample Output
12
HINT
结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12
Solution
模板splay题
而且不带删除的
发现splay静态的写法比动态的写法好很多：代码复杂度小，而且更快
本蒟蒻代码运行结果：
Accepted 2844 kb 724 ms C++/Edit 1971 B
表示不是很懂那些几十ms是怎么刷出来的？（也许那时候BZOJ的评测机比较快）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
using namespace std;
int fa[MAXN], t[MAXN][2], val[MAXN];
int n, size, root = 0, x1, x2;
inline void Rotate(int x, int &k)
{
int y = fa[x], z = fa[y], l, r;
if (t[y][0] == x) l = 0; else l = 1;
r = l ^ 1;
if (k == y) k = x; //如果要旋转到的节点已经是它的父节点，就将要旋转到的节点(通常是根)改为x
else t[z][t[z][1] == y] = x; //如果z的右孩子是y，那么就将右孩子改为x，否则将左孩子改为x，右孩子不变
fa[x] = z, fa[y] = x;
fa[t[x][r]] = y;
t[y][l] = t[x][r];
t[x][r] = y;
}
inline void Splay(int x, int &k)
{
while (x != k)
{
int y = fa[x], z = fa[y];
if (y != k)
{
(t[y][0]==x) ^ (t[z][0]==y) ? Rotate(x, k) : Rotate(y, k);
}
Rotate(x, k);
}
}
inline bool ins(int &k, int x, int f)
{
if (!k)
{
k = ++size;
val[k] = x, fa[k] = f, Splay(k, root);
return 1;
}
if (val[k] == x) return 0;
if (x < val[k]) return ins(t[k][0], x, k);
else return ins(t[k][1], x, k);
}
inline void pred(int k)
{
if (!t[k][0]) return ;
k = t[k][0];
while (t[k][1]) k = t[k][1];
x1 = val[k];
}
inline void succ(int k)
{
if (!t[k][1]) return ;
k = t[k][1];
while (t[k][0]) k = t[k][0];
x2 = val[k];
}
int main(int argc, char **argv)
{
ios::sync_with_stdio(false);
int N;
int ans = 0;
cin >> N;
for (register int i = 1; i <= N; ++i)
{
int x;
cin >> x;
if (!ins(root, x, 0)) continue;
x1 = -inf, x2 = inf;
if (i == 1) ans += x;
else
{
pred(root), succ(root);
ans += min(abs(x - x1), abs(x2 - x));
}
}
cout << ans << endl;
return 0;
}